package geekstudy.week7;

/**
 * 200. 岛屿数量
 * https://leetcode-cn.com/problems/number-of-islands/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：1 ms, 在所有 Java 提交中击败了100.00% 的用户
 * 内存消耗：40.8 MB, 在所有 Java 提交中击败了58.91% 的用户
 *
 */
public class Week7NumberOfIslands {

    public int numIslands(char[][] grid) {

        if(grid == null || grid.length < 1){
            return 0;
        }
        int rowLength = grid.length;
        int columnLength = grid[0].length;

        //初始化
        int[] unionArray  = new int[rowLength * columnLength];
        for(int rowSize = 0; rowSize < rowLength; rowSize++){
            for(int columnSize = 0; columnSize < columnLength; columnSize++){
                unionArray[ rowSize * columnLength + columnSize] = rowSize * columnLength + columnSize;
            }
        }

        //并
        for(int rowSize = 0; rowSize < rowLength; rowSize++){
            for(int columnSize = 0; columnSize < columnLength; columnSize++){
                if(grid[rowSize][columnSize] == '1' ){
                    if(rowSize + 1 < rowLength && grid[rowSize + 1][columnSize] == '1') {
                        union(unionArray, rowSize * columnLength + columnSize, (rowSize + 1) * columnLength + columnSize);
                    }
                    if(columnSize + 1 < columnLength && grid[rowSize][columnSize + 1] == '1') {
                        union(unionArray, rowSize * columnLength + columnSize, rowSize * columnLength + columnSize + 1);
                    }
                }
            }
        }
        //统计并查集最顶层的节点有几个 就是有几个岛
        int count = 0;
        for(int rowSize = 0; rowSize < rowLength; rowSize++){
            for(int columnSize = 0; columnSize < columnLength; columnSize++){
                if(grid[rowSize][columnSize] == '1' && unionArray[rowSize * columnLength + columnSize] == rowSize * columnLength + columnSize){
                    count++;
                }
            }
        }
        return count;
    }

    public void union(int[] unionArray, int first,int second){
        unionArray[find(unionArray, first)] = find(unionArray, second);
    }

    public int find(int[] unionArray, int index){
        while(unionArray[index] != index){
            index= unionArray[index];
        }
        return index;
    }

}
